package com.zklh.leetcode.dynamic;

/**
 * @author ：tong nan
 * @date ：Created in 2021/10/6 15:48
 * @description ：背包问题算法实现
 * @modifiedBy ：
 */
public class KnapsackSolution {

    /**
     *
     * @param w 背包总承重
     * @param n 可选物品数量
     * @param wt 可选物品质量
     * @param val 可选物品价值
     * @return 背包能承载的最大价值
     */
    public int knapsack(int w, int n, int[] wt, int[] val) {
        // dp[n][w] 表示当承载量为w 可选物品数量为n的时候的最大承载价值,
        // 状态转移方程为 dp[n][w] = Max(dp[n-1][w], dp[n-1][w-wt[n]]+val[n])
        // 多增加一行和一列 用于限制边界
        int[][] dp = new int[n+1][w+1];
        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < w + 1; j++) {
                if (j - wt[i-1] >= 0) {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-wt[i-1]]+val[i-1]);
                } else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[n][w];
    }

    public static void main(String[] args) {
        KnapsackSolution solution = new KnapsackSolution();
        int w = 4;
        int n = 3;
        int[] wt = new int[]{2, 1, 3};
        int[] val = new int[]{4, 2, 3};
        System.out.println(solution.knapsack(w, n, wt, val));
    }
}
